/*2021.10.20 希尔排序，未解决*/

#include <iostream>

using namespace std;

void ShellSort(int A[], int n);

int main()
{
    int A[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int n = 10;

    ShellSort(A, n);

    for (int i = 0; i < 10; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

void ShellSort(int A[], int n)
{
    int temp,j;
    for (int d = n / 2; d >= 1; d = d / 2)
    {
        for (int i = 0; i < d; i++)
        {
            // for (int j = i; j + d <= n-1; j+=d)
            // {
            //     if (A[j] >= A[j + d])
            //     {
            //         temp = A[j];
            //         A[j] = A[j + d];
            //         A[j + d] = temp;
            //     }
            // }
            j = i;
            while (j + d <= n - 1)
            {
                if (A[j] >= A[j + d])
                {
                    temp = A[j];
                    A[j] = A[j + d];
                    A[j + d] = temp;
                }
                j = j + d;
            }
        }
    }
}